package 数组区间;

public class 等差数列划分_413 {
/**
 * 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

	例如，以下数列为等差数列:
	
	1, 3, 5, 7, 9
	7, 7, 7, 7
	3, -1, -5, -9
	以下数列不是等差数列。
	
	1, 1, 2, 5, 7
	 
	
	数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
	
	如果满足以下条件，则称子数组(P, Q)为等差数组：
	
	元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
	
	函数要返回数组 A 中所有为等差数组的子数组个数。
	
	 
	
	示例:
	
	A = [1, 2, 3, 4]
	
	返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
 */
	//思路:对于 (1,2,3,4)，它有三种组成递增子区间的方式，而对于 (1,2,3,4,5)，
	//它组成递增子区间的方式除了 (1,2,3,4) 的三种外还多了一种，即 (1,2,3,4,5)，因此 dp[i] = dp[i - 1] + 1。
	//(1,2,3) dp[2] =1 (1,2,3,4)dp[3] = 1+2=1+(1+1)=3  (1,2,3,4,5) dp[4] = 3+4 =3+(3+1)=7 (1,2,3,4,5,6) dp[5] = 7+8 =7+(7+1)=15
	public int numberOfArithmeticSlices(int[] A) {
	  //获取A的长度
		int n = A.length;
	    //定义一个数组
		int[] dp = new int[n];
		//从2开始
	    for(int i = 2; i < n; i++) {
	        if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
	            dp[i] = dp[i - 1] + 1;
	        }
	    }
	    //获取每一种情况上面次数就行了
	    int ret = 0;
	    for(int cnt : dp) {
	        ret += cnt;
	    }
	    return ret;
	}
}
